package algorithm.sorting.compare.mergesort;

import algorithm.sorting.ISort;
import algorithm.sorting.compare.insertsort.InsertSorter;
import java.util.ArrayList;
/**
 * @author lancyguy
 * @author cgzh@hotmail.com
 * @param <T> type of the elements to be sorted
 */
public class MergeSorter<T extends Comparable<T>> implements ISort<T>{
    /**
     * no secondary sorter used by default
     */
    public MergeSorter(){
		recursionThreshold = 1;
		secondSorter = null;//set to null cause never used
	}
    /**
     * if no secondary sorter assigned, then use insert sorter
     * @see algorithm.sorting.compare.insertsort.InsertSorter
     * @param rt recursion threshold
     */
	public MergeSorter(int rt){
		recursionThreshold = rt;
		secondSorter = new InsertSorter<T>();
	}
    /**
     * @param rt recursion threshold
     * @param sorter secondary sorter
     */
	public MergeSorter(int rt, ISort<T> sorter){
		recursionThreshold = rt;
		secondSorter = sorter;
	}
    /**
     * sort the whole array
     * @param arr array to be sorted
     */
    public void sort(T[] arr) {
        sort(arr,0,arr.length-1);
    }
    /**
     * @param arr array to be sorted
     * @param head left boundary of the range of the array within which the sorting takes place
     * @param end  right boundary of the range of the array within which the sorting takes place.
     */
    public void sort(T[] arr, int head, int end) {
    	if(arr.length==0 || head<0 || end>=arr.length || end-head<=0) 
    		return;
		if(end-head+1<this.recursionThreshold){
			secondSorter.sort(arr,head,end);
			return;
		}
        int middle = (head+end)/2;
        sort(arr,head,middle);
        sort(arr,middle+1,end);
        merge(arr,head,end,middle);
    }
    private void merge(T[] arr, int head, int end, int middle){
        ArrayList<T> tempArr = new ArrayList<T>(end-head+1);
        int leftCurrent = head;
        int rightCurrent = middle+1;
        while(true){
            if(arr[leftCurrent].compareTo(arr[rightCurrent])<=0){
                tempArr.add(arr[leftCurrent++]);
                if(leftCurrent>middle){
                    for(int i=rightCurrent;i<=end;i++)
                        tempArr.add(arr[i]);
                    break;
                }
            }
            else{
                tempArr.add(arr[rightCurrent++]);
                if(rightCurrent>end){
                    for(int i=leftCurrent;i<=middle;i++)
                        tempArr.add(arr[i]);
                    break;
                }
            }
        }
        for(int i=0;i<=end-head;i++){
            arr[head+i] = tempArr.get(i);
        }
    }
    private int recursionThreshold;  //if the size of the range below this value, use secondary Sorter to optimize the sorting.
	private ISort<T> secondSorter;   // secondary sorter
}

